package oj;

/**
 * @author 郝文雪
 * @date 2022/8/20 18:58
 * @Description Test
 */
public class LC234 {
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        ListNode lastNode=quickSlow(head);
        ListNode newHead=reverse(lastNode.next);

        ListNode p1=head;
        ListNode p2=newHead;
        boolean result=true;
        while(result && p2!=null){
            if(p1.val!=p2.val){
                return false;
            }
            p1=p1.next;
            p2=p2.next;
        }
        lastNode.next=reverse(newHead);
        return result;
    }
    private ListNode quickSlow(ListNode head){
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
    private ListNode reverse(ListNode node){
        if(node==null || node.next==null) return node;
        ListNode secHead=node.next;
        ListNode newHead=reverse(secHead);
        secHead.next=node;
        node.next=null;
        return newHead;
    }
}
